//76.最小覆盖子串
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

string minWindow(string t, string s)
{
    // 定义两个哈希表，用来建立字符和个数之间的映射关系
    unordered_map<char, int> hasht;
    unordered_map<char, int> hashs;

    // 将字符串t的字符映射到哈希表t中
    int bucket = 0;
    for (auto e : t)
    {
        hasht[e]++;
        // 统计哈希表t的字符种类
        if (hasht[e] == 1)
        {
            bucket++;
        }
    }

    // 定义左右指针，count变量记录哈希表s中的字符种类，有效字符个数
    int left = 0, right = 0;
    int count = 0;

    // begin字串的起始位置，用来更新结果，minlen记录最小字串的长度
    int begin = -1;
    int minlen = INT_MAX;

    while (right < s.size())
    {
        // 进窗口
        hashs[s[right]]++;

        // 两个哈希表中的字符映射关系相等时，count加一
        if (hashs[s[right]] == hasht[s[right]])
        {
            count++;
        }

        // 判断条件，字符种类相等
        while (count == bucket)
        {
            // 更新结果
            minlen = min(minlen, right - left + 1);
            if (minlen == right - left + 1)
            {
                begin = left;
            }

            // 出窗口
            if (hashs[s[left]] == hasht[s[left]])
            {
                count--;
            }
            hashs[s[left]]--;
            if (hashs[s[left]] == 0)
            {
                hashs.erase(s[left]);
            }
            left++;
        }

        right++;
    }

    // 如果没有找到，begin还是初始值返回空字符串，否则返回字串
    return begin == -1 ? "" : s.substr(begin, minlen);
}

int main()
{
    string t = {"a"};
    string s = {"a"};

    string ret = minWindow(t, s);
    for (auto e : ret)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}